Implement Trie

category: Tries difficulty: Medium

Cues/Questions | Notes

Problem Statement

What is a Trie? | A tree data structure used to efficiently store and retrieve keys in a dataset of strings. Also called a "prefix tree" (pronounced "try").

What operations to implement? |

insert(word) - Inserts string word into trie
search(word) - Returns true if word is in trie
startsWith(prefix) - Returns true if any word in trie starts with prefix

Example usage: |

trie = Trie()
trie.insert("apple")
trie.search("apple")     # true
trie.search("app")       # false
trie.startsWith("app")   # true
trie.insert("app")
trie.search("app")       # true

Applications? | Autocomplete, spell checker, IP routing, T9 predictive text

Key Concepts

What is the structure? |

Each node represents a character
Root is empty
Each node has up to 26 children (for lowercase a-z)
Nodes have a flag indicating if they mark end of a word

Visual representation: |

Example: insert "cat", "cap", "car"
        (root)
          |
          c
          |
          a
        / | \
       t  p  r
      *  *  *
(* = end of word marker)

Why use Trie? |

Search/Insert: O(m) where m = word length
Space efficient for many words with common prefixes
Better than hash table for prefix operations

Python Solution

TrieNode Class Design

What does a node contain? |

Dictionary/map of children nodes (key: char, value: TrieNode)
Boolean flag to mark end of word

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word
    
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Complexity Analysis

Insert - Time: | O(m) where m = length of word (traverse each character) Insert - Space: | O(m) worst case (all new nodes), O(1) average (shared prefixes) Search - Time: | O(m) where m = length of word Search - Space: | O(1) no extra space needed StartsWith - Time: | O(m) where m = length of prefix StartsWith - Space: | O(1) no extra space needed

Python specifics: |

Use dict for children - dynamic and clean
in operator for checking key existence
Can use defaultdict(TrieNode) for cleaner code

Golang Solution

TrieNode Struct Design

What does a node contain? |

Array or map of children nodes
Boolean to mark end of word
Common patterns: [26]*TrieNode (array) or map[rune]*TrieNode (map)

Code Implementation (Map-based)

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{
        root: &TrieNode{
            children: make(map[rune]*TrieNode),
            isEnd:    false,
        },
    }
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, char := range word {
        if node.children[char] == nil {
            node.children[char] = &TrieNode{
                children: make(map[rune]*TrieNode),
                isEnd:    false,
            }
        }
        node = node.children[char]
    }
    node.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, char := range word {
        if node.children[char] == nil {
            return false
        }
        node = node.children[char]
    }
    return node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, char := range prefix {
        if node.children[char] == nil {
            return false
        }
        node = node.children[char]
    }
    return true
}

Alternative (Array-based for Lowercase only)

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &TrieNode{}
        }
        node = node.children[idx]
    }
    node.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if node.children[idx] == nil {
            return false
        }
        node = node.children[idx]
    }
    return node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for i := 0; i < len(word); i++ {
        idx := prefix[i] - 'a'
        if node.children[idx] == nil {
            return false
        }
        node = node.children[idx]
    }
    return true
}

Golang specifics: |

Use rune type for Unicode support (map-based)
Array [26]*TrieNode is faster but only for lowercase a-z
Pointer receivers for methods to modify struct
Must explicitly check nil before accessing
range over string yields runes (Unicode code points)

Design Decisions

Map vs Array? |

Map: Flexible, Unicode support, sparse data
Array [26]: Faster lookup O(1), only lowercase a-z, uses more memory

When to use each? |

Map: General purpose, unknown character set, Unicode
Array: Known to be lowercase English only, performance critical

Space complexity of Trie? |

Worst case: O(ALPHABET_SIZE × N × M)
- N = number of words
- M = average length of words
Best case: O(M) when all words share same prefix
Real world: Between best and worst due to prefix sharing

Common Pitfalls

Forgetting end marker | search("app") would return true for "apple" without proper end marker

Not initializing children | Golang: Must initialize map/create new node. Python: Check before accessing

Character encoding | Assuming ASCII when input could be Unicode. Use rune in Go, Python handles automatically

Memory leaks | Not an issue in these languages, but be aware in C/C++

Summary

Core Concept: Trie is a tree where each path from root to leaf represents a word, with shared prefixes stored once

Key Operations: All three operations (insert, search, startsWith) have O(m) time complexity where m is word/prefix length

Python Strength: Clean syntax with dict, defaultdict makes code more concise

Golang Considerations: Choose between map (flexible) or array (fast), must manage pointers explicitly

Critical Difference: search() checks isEnd flag, startsWith() only checks if path exists

Interview Tips:

Explain the difference between search and startsWith clearly
Mention space optimization through prefix sharing
Discuss trade-offs between array and map implementations
Consider follow-up: delete operation (more complex - need to clean empty branches)

Real-world use: Autocomplete systems use this exact structure - typing "app" shows all words starting with "app"

Extension possibilities: Add count field for word frequency, support wildcards, implement delete operation

category: Tries difficulty: Medium​

Cues/Questions | Notes​

Problem Statement​

Key Concepts​

Python Solution​

TrieNode Class Design​

Code Implementation​

Complexity Analysis​

Golang Solution​

TrieNode Struct Design​

Code Implementation (Map-based)​

Alternative (Array-based for Lowercase only)​

Design Decisions​

Common Pitfalls​

Summary​